package org.deng.learn.basic.sort;

/**
 * @author DengLibin
 * @Description 快速排序： 介绍 http://www.cnblogs.com/redbear/p/8891730.html
 * @Date 2019/3/14 0014 17:47
 */
public class QuickSort extends Sort {

    //快速排序 传入列表、开始位置和结束位置
    public static   void quickSort(int[] arr, int start, int end){
        //如果start和end碰头了，说明要我排的这个子数列就剩下一个数了，就不用排序了
        if(start >= end){
            return;
        }
        //拿出第一个数当作基准数mid
        int mid = arr[start];
        int low = start;//low来标记左侧从基准数始找比mid大的数的位置
        int high = end;//high来标记右侧end向左找比mid小的数的位置
        //进行循环，只要low和high没有碰头就一直进行,当low和high相等说明碰头了
        while (low < high){
            /**
             * 一定先从右边往左边找 再从左边边往右边找 顺序不能变
             * */

            //从右往左找直到找到比mid小的数
            while (low < high && arr[high] > mid){
                high--;
            }
            //从左往右找直到找到比mid大的数（不包括等于的)
            while (low < high && arr[low]<= mid){
                low++;
            }
            //交换
            swap(arr, low, high);
        }
        //low和high碰头了 交换start和low 这样arr[low]左边的数比arr[low]小，右边的数比arr[low]大
        swap(arr, start, low);
        //递归左边
        quickSort(arr, start, low-1);
        //递归右边
        quickSort(arr, low+1, end);
    }
    public  static  void main(String[] args){
        int[] arr = {34,4,0,5,53,4,2,5,2,78,32};
        quickSort(arr, 0, arr.length -1);
        showArr(arr);
    }
}
